from copy import deepcopy

from utils.log import Log
from utils.bit_op import BitOp
from utils.generator import Generator
from utils.profile import Profile


class MergeSort(Log):
    def __init__(self, arr):
        super(MergeSort, self).__init__()
        self.arr = arr
        self.arr_backup = deepcopy(arr)
        self.len = len(arr)

    @Profile(log=False)
    def sort(self, left=None, right=None):
        left = 0 if left is None else left
        right = self.len - 1 if right is None else right
        if left == right:
            return
        middle = BitOp.middle(left, right)
        self.sort(left, middle)
        self.sort(middle + 1, right)
        self.merge(left, middle, right)

    @Profile()
    def sort_non_recursive(self):
        # https://www.bilibili.com/video/BV1wu411p7r7/?spm_id_from=autoNext&vd_source=ad559e41b561d48861f70d0187e51e02
        # 25:00
        step = 1
        # 一共需要log(N)次
        while step < self.len:
            left = 0
            # 每次的时间复杂度是N
            while left < self.len:
                middle = left + step - 1
                if middle + 1 >= self.len:
                    break
                right = min(left + (step << 1) - 1, self.len - 1)
                self.merge(left, middle, right)
                left = right + 1
            step <<= 1

    @Profile()
    def merge(self, left, middle, right):
        if left + 1 == right:
            if self.arr[left] > self.arr[right]:
                self.arr[left], self.arr[right] = self.arr[right], self.arr[left]
            return
        index = left
        left_index = left
        right_index = middle + 1
        while (left_index <= middle) and (right_index <= right):
            if self.arr[left_index] <= self.arr[right_index]:
                self.arr_backup[index] = self.arr[left_index]
                left_index += 1
            else:
                self.arr_backup[index] = self.arr[right_index]
                right_index += 1
            index += 1
        while left_index <= middle:
            self.arr_backup[index] = self.arr[left_index]
            left_index += 1
            index += 1
        while right_index <= right:
            self.arr_backup[index] = self.arr[right_index]
            right_index += 1
            index += 1
        self.arr[left: right + 1] = deepcopy(self.arr_backup[left: right + 1])


if __name__ == '__main__':
    arr = Generator().do()
    arr2 = deepcopy(arr)
    MergeSort(arr).sort()
    Profile().print_and_reset()
    MergeSort(arr2).sort_non_recursive()
    print(arr)
    print(arr2)
    print(arr == arr2)
    Profile().print_and_reset()

    arr_desc = Generator(asc=False).do()
    arr_desc2 = deepcopy(arr_desc)
    MergeSort(arr_desc).sort()
    Profile().print_and_reset()
    MergeSort(arr_desc2).sort_non_recursive()
    print(arr_desc)
    print(arr_desc2)
    print(arr_desc == arr_desc2)
